package array

import (
	"math"
)

/**
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

思路：使用单调递栈原理
*/
func largestRectangleArea(heights []int) int {
	heights = append(heights, -1) //添加哨兵位置，用来让栈弹出，因为-1边界最小了，满足最小栈弹出的需求
	stack := []int{-1}            //模拟栈  记录的是高度值在heights中的下标
	// 添加-1的哨兵位，因为弹出heights第一个元素的 防止下边越界 //压入-1为方便计算打头位置的面积
	res := 0
	for i := 0; i < len(heights); i++ {
		for len(stack) > 1 && heights[stack[len(stack)-1]] > heights[i] { //比i处height值的之前左边界都找到了右边界 弹出计算面积
			//右边界高更小了，出栈 计算面积（高度变小，面积不可能变大了）
			topH := stack[len(stack)-1]
			stack = stack[:len(stack)-1] //弹栈
			for len(stack) > 1 && heights[stack[len(stack)-1]] == heights[topH] {
				stack = stack[:len(stack)-1] //弹栈
			}
			//左边界（栈顶元素的后一个元素）
			//右边界就是i
			//高度就是以栈顶元素为下标的柱子的高度
			//左边界就是栈顶元素的下一位元素（因为我们添加了哨兵-1，所以这公式依旧成立）
			width := i - stack[len(stack)-1] - 1
			res = max(width*heights[topH], res)
		}
		stack = append(stack, i)
	}
	return res
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/**
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。



示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

*/
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	isON := (len(nums1)+len(nums2))%2 != 0 //奇数个数字
	var calAvg func(a, lastVal int) float64
	calAvg = func(a, lastVal int) float64 {
		if isON {
			return float64(a)
		}
		return (float64(a) + float64(lastVal)) / 2
	}
	mid := (len(nums1) + len(nums2)) / 2
	ia, ib := 0, 0
	lastVal := 0
	result := float64(0)
	index := 0
	for ia < len(nums1) && ib < len(nums2) {
		if nums1[ia] > nums2[ib] {
			if index == mid {
				//到达中位数位置，从0开始的所以要+1
				return calAvg(nums2[ib], lastVal)
			} else {
				lastVal = nums2[ib]
				ib++
			}
		} else {
			if index == mid {
				//到达中位数位置，从0开始的所以要+1
				return calAvg(nums1[ia], lastVal)
			} else {
				lastVal = nums1[ia]
				ia++
			}
		}
		index++
	}
	//遍历nums1剩下的
	for ia < len(nums1) {
		if index == mid {
			//到达中位数位置，从0开始的所以要+1
			result = calAvg(nums1[ia], lastVal)
			break
		} else {
			lastVal = nums1[ia]
			ia++
		}
		index++
	}
	//遍历nums2剩下的
	for ib < len(nums2) {
		if index == mid {
			//到达中位数位置，从0开始的所以要+1
			result = calAvg(nums2[ib], lastVal)
			break
		} else {
			lastVal = nums2[ib]
			ib++
		}
		index++
	}
	return result
}

/**
盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

*/
func maxArea(height []int) int {
	left, right := 0, len(height)-1
	maxArea := 0
	for left <= right {
		if height[left] < height[right] {
			maxArea = max((right-left)*height[left], maxArea)
			left++
		} else {
			maxArea = max((right-left)*height[right], maxArea)
			right--
		}
	}
	return maxArea
}

/**
搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

解题思路：
根据nums[0]来判断target在左段还是右段，如果判定了在左段，则更改mid下标在原数组的中的数据为intmax或intmin，然后把二分搜索一步步逼近左边一段或者右边一段进行搜索
*/

func search(nums []int, target int) int {
	low := 0
	height := len(nums) - 1
	for low <= height {
		mid := (height-low)>>1 + low
		if target == nums[mid] {
			return mid
		}
		//根据 nums[0]和target的关系，判定查找应该在左段还是又锻
		if nums[0] > target {
			//target 在右段 查找在左端
			if nums[mid] >= nums[0] {
				nums[mid] = math.MinInt32
			}
		} else {
			//target在左段 查找在右端 将查找无限逼向左端(右边都设置max最大值)
			if nums[mid] < nums[0] {
				nums[mid] = math.MaxInt32
			}
		}
		if nums[mid] < target {
			low = mid + 1
		} else {
			height = mid - 1
		}

	}
	return -1
}

/**
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

*/
func removeElement(nums []int, val int) int {
	//1 2 3 1 |1 1 2 3 :1
	//1 2 3 :2
	rCount := 0
	rIndex := -1
	for i := 0; i < len(nums); i++ {
		if nums[i] == val {
			if rIndex < 0 {
				//删除 标记位置
				rIndex = i
			}
			//else 存在删除标记时，如果当前元素需要删除，忽略即使删除，当遇到非删元素放到rindex
			rCount++
		} else {
			//rindex <0时说明还没有软删除的坑位
			if rIndex >= 0 {
				//调整元素到 软删除产生的坑位
				//rindex=-1 表示 下标0位置被删除了(首位数据)，此时无须提元素
				nums[rIndex] = nums[i] //不删除的元素 往前提，放到删除位置的坑里
				rIndex++
			}
		}
	}
	return len(nums) - rCount
}
func searchInsert(nums []int, target int) int {
	if target > nums[len(nums)-1] {
		//比有序数组最后一个元素大，直接返回末尾+1作为插入位置
		return len(nums)
	}
	left := 0
	right := len(nums) - 1
	for left <= right {
		mid := left + (right-left)/2
		if target < nums[mid] {
			//下一轮搜索的区间是 [left..mid]
			right = mid - 1
		} else if target == nums[mid] {
			return mid
		} else {
			//下一轮搜索的区间是 [mid + 1..right]
			left = mid + 1
		}
	}
	return left

}
